package main.leetcode.clockin.April;

import java.util.HashMap;

/** day5的优化，太长了所以另建一个 */
public class day5II {
    private HashMap<Integer, ListNode> cache;
    private HashMap<Integer, DoublyLinkList> frequentMap;
    private int capacity;
    private int min;

    public day5II(int capacity) {
        cache = new HashMap<>(capacity);
        frequentMap = new HashMap<>();
        this.capacity = capacity;
    }

    public static void main(String[] args) {
        day5II cache = new day5II(0);
        //        cache.put(1, 1);
        //        cache.put(2, 2);
        //        System.out.println(cache.get(1)); // 1
        //        cache.put(3, 3); // 去除 key 2
        //        System.out.println(cache.get(2)); // -1
        //        System.out.println(cache.get(3)); // 3
        //        cache.put(4, 4); // 去除 key 1
        //        System.out.println(cache.get(1)); // -1
        //        System.out.println(cache.get(3)); // 3
        //        System.out.println(cache.get(4)); // 4
        cache.put(2, 1);
        System.out.println(cache.get(2));
        cache.put(3, 2);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
    }

    public int get(int key) {
        if (cache.size() == 0 || !cache.containsKey(key)) return -1;
        ListNode node = cache.get(key);
        updateFreq(node, node.count);
        return node.value;
    }

    public void put(int key, int value) {
        if (capacity == 0) return;
        if (cache.containsKey(key)) {
            ListNode node = cache.get(key);
            node.value = value;
            updateFreq(node, node.count);
            cache.put(key, node);
        } else {
            // 达到最大容量，移除
            if (cache.size() == capacity) cacheRemove();
            ListNode node = new ListNode(key, value);
            updateFreq(node, 0);
            cache.put(key, node);
            min = 1;
        }
    }

    private void cacheRemove() {
        DoublyLinkList list = frequentMap.get(min);
        int key = list.removeTail();
        cache.remove(key);
    }

    private void updateFreq(ListNode node, int oldFreq) {
        ++node.count;

        // 从旧的频次队列移除（新增节点不用）
        if (oldFreq != 0) {
            DoublyLinkList oldList = frequentMap.get(oldFreq);
            oldList.remove(node);
            if (oldList.size == 0 && oldFreq == min) min = oldFreq + 1;
        }

        // 放入新的频次队列
        DoublyLinkList newList = frequentMap.get(oldFreq + 1);
        if (newList == null) {
            newList = new DoublyLinkList();
            frequentMap.put(oldFreq + 1, newList);
        }
        newList.add2First(node);
    }

    private class ListNode {
        int key;
        int value;
        int count = 0;
        ListNode next;
        ListNode pre;

        ListNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private class DoublyLinkList {
        ListNode head;
        ListNode tail;
        int size;

        public DoublyLinkList() {
            head = new ListNode(-1, -1);
            tail = new ListNode(-1, -1);
            head.next = tail;
            tail.pre = head;
            size = 0;
        }

        void remove(ListNode node) {
            ListNode pre = node.pre;
            ListNode next = node.next;
            pre.next = next;
            next.pre = pre;
            --size;
        }

        int removeTail() {
            int key = tail.pre.key;
            ListNode pre = tail.pre.pre;
            pre.next = tail;
            tail.pre = pre;
            --size;
            return key;
        }

        void add2First(ListNode node) {
            ListNode next = head.next;
            node.next = next;
            next.pre = node;
            head.next = node;
            node.pre = head;
            ++size;
        }
    }
}
